package com.qh.xx.二叉树;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 左右子树都交换
 * https://leetcode-cn.com/problems/invert-binary-tree/
 *
 * @description:
 * @author: zqh
 * @date: 2021/11/7 23:38
 **/
public class _226_翻转二叉树 {

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        // public TreeNode invertTree(TreeNode root) {
        //     if (root == null) {
        //         return root;
        //     }
        //
        //     TreeNode tmp = root.left;
        //     root.left = root.right;
        //     root.right = tmp;
        //
        //     invertTree(root.left);
        //     invertTree(root.right);
        //     return root;
        // }

        // public TreeNode invertTree(TreeNode root) {
        //     if (root == null) {
        //         return root;
        //     }
        //
        //     invertTree(root.left);
        //     invertTree(root.right);
        //
        //     TreeNode tmp = root.left;
        //     root.left = root.right;
        //     root.right = tmp;
        //     return root;
        // }

        // public TreeNode invertTree(TreeNode root) {
        //     if (root == null) {
        //         return root;
        //     }
        //
        //     invertTree(root.left);
        //
        //     TreeNode tmp = root.left;
        //     root.left = root.right;
        //     root.right = tmp;
        //
        //     invertTree(root.left);
        //
        //     return root;
        // }


        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return root;
            }

            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                TreeNode tmp = root.left;
                root.left = root.right;
                root.right = tmp;

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            return root;
        }
    }
}
